In the field of data communications there are many examples of chassis based communication devices. A chassis based communication device features a series of modular components; typically a chassis (or enclosure), a backplane and a series of add-in circuit cards. Together chassis and backplane typically provide a series of slots into which the add-in cards can be installed. The backplane provides a series of connections between slots to allow communication between cards in different slots. The topology of the connections on the backplane varies from system to system. One common topology is referred to as a dual star. In the dual star topology, the backplane provides two links to each slot of the backplane. Each link terminates on one of two dedicated slots in the system. These slots are commonly referred to as switch or hub slots. This configuration is referred to as a dual star because there are two stars of links each centered by a switch card. The two switch cards are provided for redundancy. As an example, such a system has been standardized by the PCI Industrial Computer Manufacturers Group (PICMG) as the PCIMG 3.0 standard, the contents of which are included by reference.
The switch slots are so called because they typically contain a series of components that logically connect the other slots in the system for the purpose of slot to slot communications, known as a switch fabric. The switch fabric may also contain components that reside on cards other than the switch card; these components are commonly known as the fabric interface. In currently existing systems the switch fabric components are typically purpose built application specific integrated circuits (ASICs) or application specific standard products (ASSPs) as they are known in the art. An emerging trend is the application of standard networking technologies to the switch fabric function; technologies such as Ethernet, Infiniband or Fibre Channel but may include others. Designing a system that incorporates these technologies is desirable because they present standard interfaces to other system components; this allows for other components to be sourced from multiple vendors. Standard networking technologies also have the advantage of low cost, primarily because they are heavily mass produced. However, the advantages that these technologies enjoy compared to the purpose built switch fabrics (in the embedded data communications application) are in many cases out weighed by a lack of features; such as redundancy and switch congestion management.
Chassis based communication devices typically fall into a category of devices know as high availability systems. High availability systems are often required to be operational 99.999% of the time. In order to achieve these stringent requirements for system availability products built to these standards must feature redundancy for all components as well as the ability to repair the system without taking it offline. The switch card of a chassis based multi card communication device is an example of such a component; as such redundancy is required. Purpose built switch fabric chipsets typically support redundancy as a feature. Redundancy is typically supported by a combination of the switch fabric components residing on the switch cards as well as the fabric interface components that reside on the other cards of the system.
Methods of providing switch redundancy of similar systems using an Ethernet fabric are described in U.S. Pat. No. 6,675,254 herein included by reference; here a method of providing redundancy by replicating frames and transporting them over parallel Ethernet switches is described. Previous methods lack a simple way for the destination to determine on a frame by frame basis which copy of each frame to receive. Higher layer protocols such as TCP employ sequence numbers to make them resilient to the reception of duplicate frames but, removing the duplicates by these methods would unnecessarily burden the application terminating TCP; a simple algorithm suitable to implementation in hardware that is able to remove the duplicate frames before they are transferred to the application is desirable.
A purpose built switch fabric for a chassis based communication device will typically implement one or more method(s) of avoiding congestion as a feature. These methods are designed to minimize the amount of data loss within the switch fabric (ideally to 0) while maximizing throughput. These methods also typically provide for some level of quality of service to prevent head of line blocking, as is known in the art, where congestion of low priority traffic impacts the performance of higher priority traffic. Standard networking technologies are less advanced with respect to congestion avoidance than switch fabrics built for the purpose of providing connectivity between cards of a chassis based communication device. Standard networking technologies have generally been built with simple congestion avoidance mechanisms designed to scale to large numbers of devices rather than provide good performance with respect to loss rate and throughput. These technologies rely on higher layer protocols to recover from data loss. For example the congestion avoidance mechanism employed by Ethernet is the pause frame. When an Ethernet switch is experiencing congestion it may issue a pause frame to endpoints (data sources) that are thought to be the cause of the congestion. Upon the reception of a pause frame an endpoint is required to stop sending data for a period of time (indicated in the pause frame) to allow time for the congestion in the switch to be relieved. The endpoint is required to stop transmitting all data even if it has data destined for endpoints not affected by the congestion of the switch. This phenomenon is referred to as head of line blocking and it represents a loss of throughput in the switch. Purpose built switch fabrics avoid head of line blocking by implementing a system of virtual output queues (VOQs); these techniques are well known in the art. Typically the VOQs are contained within a switch fabric interface device or traffic manager contained on the each card in the system (excluding the switch cards). A discussion of virtual output queuing in context of implementing networking devices using buffered crossbar switches is included in Shang-Tse Chuang, Sundar Iyer, Nick McKeown; “Practical Algorithms for Performance Guarantees in Buffered Crossbars”, Proceedings of IEEE INFOCOM 2005, Miami, Fla., March 2005, the contents of which are included by reference.
In a system employing virtual output queues each source of data into the switch implements a separate queue per destination endpoint; each of these queues can respond to backpressure independent of all the other queues. By this mechanism the switch fabric can assert backpressure only to the queues where the destination endpoint is congested; allowing data to continue to be transmitted to endpoints that are not currently experiencing congestion. The use of virtual output queues with backpressure (or flow control) eliminates the head of line blocking and increases throughput in the switch while limiting data loss in the switch due to congestion.
A high performance switch fabric can be constructed using standards based switching devices as a type of buffered crossbar element as they are known in the art. At each endpoint a simple distributed scheduling algorithm is implemented; backpressure (or flow control) using backward congestion notification techniques also know in the art are used to combat congestion in the crossbar element and at the destination endpoints. This invention implements hardware to interpret backward congestion notification frames reducing latency inherent to software only implementations; latency in the flow control feedback loop reduces the effectiveness of these techniques. The hardware methods described are designed to interoperate with a variety of devices such as network processors or traffic managers that are available in the marketplace; the ability to work with preexisting (building block) devices offers a great deal of design flexibility.